package sort;

import java.util.Arrays;

/**
 * @Author: Dang Qi
 * @Date: 2021/4/7  16:49
 * @Description:
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] a= {5,2,6,4,7,8};
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
    public static void heapSort(int[] a){
        buildHeap(a);
        int N = a.length;
        for(int i = a.length-1; i >=1; i--){
            swap(a, i, 0);
            adjustHeap(a,  0, --N);
        }
    }
    public static void buildHeap(int[] a){
        for(int i = a.length/2; i >= 0 ; i--){
            adjustHeap(a, i, a.length);
        }
    }
    public static void adjustHeap(int[] a, int i, int N){
        int max = i;
        while (i < N){
            if(2*i+1 < N && a[max] < a[2*i+1]) max = 2*i+1;
            if(2*i+2 < N && a[max] < a[2*i+2]) max = 2*i+2;
            if(max!=i){
                swap(a, i, max);
                i = max;
            }else break;
        }
    }
    public static void swap(int[] a, int i, int j){
        if(i==j || a[i] == a[j]) return;
        a[i] = a[i] ^ a[j];
        a[j] = a[i] ^ a[j];
        a[i] = a[i] ^ a[j];
    }
}
